{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #课程表 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #topological-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #拓扑排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findOrder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #课程表 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现在总共有 <code>numCourses</code>&nbsp;门课需要选，记为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>numCourses-1</code>。</p>\n",
    "\n",
    "<p>给定一个数组&nbsp;<code>prerequisites</code> ，它的每一个元素&nbsp;<code>prerequisites[i]</code>&nbsp;表示两门课程之间的先修顺序。&nbsp;例如&nbsp;<code>prerequisites[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示想要学习课程 <code>a<sub>i</sub></code>&nbsp;，需要先完成课程 <code>b<sub>i</sub></code>&nbsp;。</p>\n",
    "\n",
    "<p>请根据给出的总课程数 &nbsp;<code>numCourses</code> 和表示先修顺序的&nbsp;<code>prerequisites</code>&nbsp;得出一个可行的修课序列。</p>\n",
    "\n",
    "<p>可能会有多个正确的顺序，只要任意返回一种就可以了。如果不可能完成所有课程，返回一个空数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> numCourses = 2, prerequisites = [[1,0]] \n",
    "<strong>输出: </strong><code>[0,1]</code>\n",
    "<strong>解释:</strong>&nbsp;总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 <code>[0,1] 。</code></pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]\n",
    "<strong>输出: </strong><code>[0,1,2,3] or [0,2,1,3]</code>\n",
    "<strong>解释:</strong>&nbsp;总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。\n",
    "&nbsp;因此，一个正确的课程顺序是&nbsp;<code>[0,1,2,3]</code> 。另一个正确的排序是&nbsp;<code>[0,2,1,3]</code> 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> numCourses = 1, prerequisites = [] \n",
    "<strong>输出: </strong><code>[0]</code>\n",
    "<strong>解释:</strong>&nbsp;总共 1 门课，直接修第一门课就可。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= numCourses &lt;= 2000</code></li>\n",
    "\t<li><code>0 &lt;= prerequisites.length &lt;= numCourses * (numCourses - 1)</code></li>\n",
    "\t<li><code>prerequisites[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= ai, bi &lt; numCourses</code></li>\n",
    "\t<li><code>ai != bi</code></li>\n",
    "\t<li><code>prerequisites</code>&nbsp;中不存在重复元素</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 210&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/course-schedule-ii/\">https://leetcode-cn.com/problems/course-schedule-ii/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [QA2IGt](https://leetcode.cn/problems/QA2IGt/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [QA2IGt](https://leetcode.cn/problems/QA2IGt/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # 存储有向图\n",
    "        edges = collections.defaultdict(list)\n",
    "        # 存储每个节点的入度\n",
    "        indeg = [0] * numCourses\n",
    "        # 存储答案\n",
    "        result = list()\n",
    "\n",
    "        for info in prerequisites:\n",
    "            edges[info[1]].append(info[0])\n",
    "            indeg[info[0]] += 1\n",
    "        \n",
    "        # 将所有入度为 0 的节点放入队列中\n",
    "        q = collections.deque([u for u in range(numCourses) if indeg[u] == 0])\n",
    "\n",
    "        while q:\n",
    "            # 从队首取出一个节点\n",
    "            u = q.popleft()\n",
    "            # 放入答案中\n",
    "            result.append(u)\n",
    "            for v in edges[u]:\n",
    "                indeg[v] -= 1\n",
    "                # 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了\n",
    "                if indeg[v] == 0:\n",
    "                    q.append(v)\n",
    "\n",
    "        if len(result) != numCourses:\n",
    "            result = list()\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        deg = [0] * numCourses\n",
    "        g = [[] for _ in range(numCourses)]\n",
    "        for a, b in prerequisites:\n",
    "            deg[a] += 1\n",
    "            g[b].append(a)\n",
    "        ans = []\n",
    "        q = deque()\n",
    "        for i, x in enumerate(deg):\n",
    "            if x == 0:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            ans.append(x)\n",
    "            for y in g[x]:\n",
    "                deg[y] -= 1\n",
    "                if deg[y] == 0:\n",
    "                    q.append(y)\n",
    "        return ans if len(ans) == numCourses else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def buildgraph(self, numCourses, prerequisites):\n",
    "        graph = [[] for _ in range(numCourses)]\n",
    "        for each in prerequisites:\n",
    "            fr = each[1]\n",
    "            t = each[0]\n",
    "            graph[fr].append(t)\n",
    "        return graph\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        graph = self.buildgraph(numCourses, prerequisites)\n",
    "        que = deque()\n",
    "        indegree = [0] * numCourses\n",
    "        res = []\n",
    "        count = 0\n",
    "        for each in prerequisites:\n",
    "            fr = each[1]\n",
    "            t = each[0]\n",
    "            indegree[t] += 1\n",
    "        for i, each in enumerate(indegree):\n",
    "            if each == 0:\n",
    "                que.append(i)\n",
    "        while que:\n",
    "            lenth = len(que)\n",
    "            for i in range(lenth):\n",
    "                cur = que.popleft()\n",
    "                res.append(cur)\n",
    "                count += 1\n",
    "                for x in graph[cur]:\n",
    "                    indegree[x] -= 1\n",
    "                    if indegree[x] == 0:\n",
    "                        que.append(x)\n",
    "        if count != numCourses:\n",
    "            return []\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        requistites=defaultdict(list)\n",
    "        num=defaultdict(int)\n",
    "        res=[]\n",
    "        temp=[]\n",
    "        for k,v in prerequisites:\n",
    "            requistites[v].append(k)\n",
    "            num[k]+=1\n",
    "        for i in range(numCourses):\n",
    "            if(num[i]==0):\n",
    "                temp.append(i)\n",
    "        while temp:\n",
    "            for _ in temp:\n",
    "                tmp=temp.pop()\n",
    "                res.append(tmp)\n",
    "                for j in requistites[tmp]:\n",
    "                    num[j]-=1\n",
    "                    if(num[j]==0):\n",
    "                        temp.append(j)\n",
    "                \n",
    "        return res if len(res)==numCourses else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        depend = [[] for x in range(numCourses)]\n",
    "\n",
    "        for x,y in prerequisites:\n",
    "            depend[x].append(y)\n",
    "        \n",
    "        temp = []\n",
    "        for x in range(numCourses):\n",
    "            if depend[x] == []:\n",
    "                temp.append(x)\n",
    "\n",
    "        while True:\n",
    "            sign = 0\n",
    "            for x in range(numCourses):\n",
    "                if depend[x]:\n",
    "                    for y in depend[x]:\n",
    "                        if depend[y] == []:\n",
    "                            depend[x].remove(y)\n",
    "                            sign = 1\n",
    "                            if depend[x] == []:\n",
    "                                temp.append(x)\n",
    "                        \n",
    "            if sign == 0:\n",
    "                break\n",
    "        print(temp)\n",
    "        if len(temp) == numCourses:\n",
    "            return temp\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        HashTable = defaultdict(list)\n",
    "        invec = [0] * numCourses\n",
    "        for i in range(len(prerequisites)):\n",
    "            HashTable[prerequisites[i][1]].append(prerequisites[i][0])\n",
    "            invec[prerequisites[i][0]] += 1\n",
    "\n",
    "        que=[]\n",
    "        for i in range(numCourses):\n",
    "            if invec[i]==0:\n",
    "                que.append(i)\n",
    "\n",
    "        ans =[]\n",
    "        while True:\n",
    "            if not que:\n",
    "                break\n",
    "            now = que.pop(0)\n",
    "            ans.append(now)\n",
    "            for ele in HashTable[now]:\n",
    "                invec[ele] -= 1\n",
    "                if invec[ele] == 0:\n",
    "                    que.append(ele)\n",
    "        if len(ans) != numCourses:\n",
    "            return []\n",
    "        else:\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        nb = defaultdict(list)\n",
    "        deg = [0] * numCourses\n",
    "\n",
    "        for a, b in prerequisites:\n",
    "            deg[a] += 1\n",
    "            nb[b].append(a)\n",
    "        \n",
    "\n",
    "        q = deque()\n",
    "        nq = deque()\n",
    "        ans = []\n",
    "        for i in range(numCourses):\n",
    "            if deg[i] == 0:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            \n",
    "            tmp = q.popleft()\n",
    "            ans.append(tmp)\n",
    "\n",
    "            for ch in nb[tmp]:\n",
    "                deg[ch] -= 1\n",
    "                if deg[ch] == 0:\n",
    "                    nq.append(ch)\n",
    "            if not q:\n",
    "                q = nq\n",
    "                nq = deque()\n",
    "        if len(ans) < numCourses:\n",
    "            return []\n",
    "        else:\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        indegree = [0] * numCourses\n",
    "        adjacency = [[] for i in range(numCourses)]\n",
    "        for cur, pre in prerequisites:\n",
    "            indegree[cur] += 1\n",
    "            adjacency[pre].append(cur)\n",
    "        queue = collections.deque()\n",
    "        res = []\n",
    "        for i in range(len(indegree)):\n",
    "            if indegree[i] == 0:\n",
    "                res.append(i)\n",
    "                queue.append(i)\n",
    "        if not queue:\n",
    "            return []\n",
    "        while queue:\n",
    "            numCourses -= 1\n",
    "            for cur in adjacency[queue.popleft()]:\n",
    "                indegree[cur] -= 1\n",
    "                if indegree[cur] == 0:\n",
    "                    res.append(cur)\n",
    "                    queue.append(cur)\n",
    "        if numCourses:\n",
    "            return []\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        prerequisiteList = collections.defaultdict(list) # 保存课程的后置节点\n",
    "        needCoursesCnt = collections.defaultdict(int) # 保存某课程的出度\n",
    "        stack = [] # 临时存放的栈，用队列也行\n",
    "        res = [] # 获取结果\n",
    "\n",
    "        for k, v in enumerate(prerequisites): # 更新入度和后置节点，相当于形成边\n",
    "            prerequisiteList[v[1]].append(v[0])\n",
    "            needCoursesCnt[v[0]] += 1\n",
    "        \n",
    "        for i in range(numCourses): # 找到入度为0的节点\n",
    "            if needCoursesCnt[i] == 0:\n",
    "                stack.append(i)\n",
    "\n",
    "        while stack: # 每次任选一个入度为0的节点\n",
    "            for _ in stack:\n",
    "                p = stack.pop()\n",
    "                res.append(p)\n",
    "                for j in prerequisiteList[p]:\n",
    "                    needCoursesCnt[j] -= 1\n",
    "                    if needCoursesCnt[j] == 0:\n",
    "                        stack.append(j)\n",
    "        # 判断是否有环\n",
    "        return res if len(res) == numCourses else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        sign = [0 for _ in range(numCourses)]\n",
    "        std = [[] for _ in range(numCourses)]\n",
    "        for x,y in prerequisites:\n",
    "            sign[x]+=1\n",
    "            std[x].append(y)\n",
    "        queue = []\n",
    "        for x in range(len(sign)):\n",
    "            if sign[x] == 0:\n",
    "                queue.append(x)\n",
    "        temp = []\n",
    "        while queue:\n",
    "            data = queue.pop()\n",
    "            temp.append(data)\n",
    "            numCourses-=1\n",
    "            for x in range(len(std)):\n",
    "                if sign[x]:\n",
    "                    if data in std[x]:\n",
    "                        sign[x] -= 1\n",
    "                        if sign[x] == 0:\n",
    "                            queue.append(x)\n",
    "\n",
    "\n",
    "        if numCourses:\n",
    "            return []\n",
    "        else:\n",
    "            return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        sign = [0 for _ in range(numCourses)]\n",
    "        std = [[] for _ in range(numCourses)]\n",
    "        for x,y in prerequisites:\n",
    "            sign[x]+=1\n",
    "            std[y].append(x)\n",
    "        queue = []\n",
    "        for x in range(len(sign)):\n",
    "            if sign[x] == 0:\n",
    "                queue.append(x)\n",
    "        temp = []\n",
    "        while queue:\n",
    "            data = queue.pop()\n",
    "            temp.append(data)\n",
    "            numCourses-=1\n",
    "            for x in std[data]:\n",
    "                if sign[x]:\n",
    "                    sign[x] -= 1\n",
    "                    if sign[x] == 0:\n",
    "                        queue.append(x)\n",
    "\n",
    "\n",
    "        if numCourses:\n",
    "            return []\n",
    "        else:\n",
    "            return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        graph = [[] for _ in range(numCourses)]\n",
    "        indegree = [0]*numCourses\n",
    "        for req in prerequisites:\n",
    "            graph[req[1]].append(req[0])\n",
    "            indegree[req[0]] += 1\n",
    "        \n",
    "        res = []\n",
    "        q = []\n",
    "        for i, num in enumerate(indegree):\n",
    "            if num == 0:\n",
    "                q.append(i)\n",
    "\n",
    "        while q:\n",
    "            cur = q.pop(0)\n",
    "            res.append(cur)\n",
    "            for node in graph[cur]:\n",
    "                indegree[node] -= 1 \n",
    "                if indegree[node] == 0:\n",
    "                    q.append(node)\n",
    "\n",
    "        if len(res) < numCourses:\n",
    "            return []\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        dic = {}\n",
    "        topsort = []\n",
    "        judge = [False] * numCourses\n",
    "        temp = [0] * numCourses\n",
    "        for edge in prerequisites:\n",
    "            temp[edge[0]] += 1\n",
    "            if edge[1] not in dic:\n",
    "                dic[edge[1]] = [edge[0]]\n",
    "            else:\n",
    "                dic[edge[1]].append(edge[0])\n",
    "        flag = True\n",
    "        while flag:\n",
    "            flag = False\n",
    "            for i in range(numCourses):\n",
    "                if temp[i] == 0 and not judge[i]:\n",
    "                    judge[i] = True\n",
    "                    topsort.append(i)\n",
    "                    if i in dic:\n",
    "                        for j in dic[i]:\n",
    "                            temp[j] -= 1\n",
    "                    flag = True\n",
    "        if len(topsort) == numCourses:\n",
    "            return topsort\n",
    "        else:\n",
    "            return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # graph\n",
    "        edges = collections.defaultdict(list)\n",
    "\n",
    "        # in degree\n",
    "        indeg = [0 for _ in range(numCourses)]\n",
    "\n",
    "        # record\n",
    "        re = []\n",
    "\n",
    "        for pair in prerequisites:\n",
    "            edges[pair[1]].append(pair[0])\n",
    "            indeg[pair[0]] += 1\n",
    "\n",
    "        q = [i for i in range(numCourses) if indeg[i] == 0]\n",
    "\n",
    "        while len(q) > 0:\n",
    "            top = q[0]\n",
    "            q = q[1:]\n",
    "            re.append(top)\n",
    "            for nex in edges[top]:\n",
    "                indeg[nex] -= 1\n",
    "                if indeg[nex] == 0:\n",
    "                    q.append(nex)\n",
    "\n",
    "        if len(re) == numCourses:\n",
    "            return re\n",
    "        return []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        prerequisitesList = defaultdict(list)\n",
    "        needCoursesCnt = defaultdict(int)\n",
    "        stack = []\n",
    "        res = []\n",
    "\n",
    "        for k, v in enumerate(prerequisites):\n",
    "            prerequisitesList[v[1]].append(v[0])\n",
    "            needCoursesCnt[v[0]] += 1\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            if needCoursesCnt[i] == 0:\n",
    "                stack.append(i)\n",
    "\n",
    "        while stack:\n",
    "            num = stack.pop()\n",
    "            res.append(num)\n",
    "            for n in prerequisitesList[num]:\n",
    "                needCoursesCnt[n] -= 1\n",
    "                if needCoursesCnt[n] == 0:\n",
    "                    stack.append(n)\n",
    "\n",
    "        return res if len(res) == numCourses else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        if not prerequisites:\n",
    "            return [i for i in range(numCourses)]\n",
    "\n",
    "        in_degrees=[0 for _ in range(numCourses)]\n",
    "        adj=[set() for _ in range(numCourses)]\n",
    "\n",
    "        for sec,fir in prerequisites:\n",
    "            in_degrees[sec]+=1\n",
    "            adj[fir].add(sec)\n",
    "        \n",
    "        queue=[]\n",
    "        res=[]\n",
    "        for i in range(numCourses):\n",
    "            if in_degrees[i]==0:\n",
    "                queue.append(i)\n",
    "        \n",
    "        while queue:\n",
    "            cur=queue.pop(0)\n",
    "            res.append(cur)\n",
    "\n",
    "            for sub in adj[cur]:\n",
    "                in_degrees[sub]-=1\n",
    "                if in_degrees[sub]==0:\n",
    "                    queue.append(sub)\n",
    "        \n",
    "        if len(res)!=numCourses:\n",
    "            return []\n",
    "        else:\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites) :\n",
    "        dic1={}\n",
    "        dic2={}\n",
    "        for i in range(numCourses):\n",
    "            dic2[i]=0\n",
    "        #创建两个表\n",
    "        for item in prerequisites:\n",
    "            if item[1] not in dic1:\n",
    "                dic1[item[1]]=[]\n",
    "            dic1[item[1]].append(item[0])\n",
    "            dic2[item[0]]+=1\n",
    "        # 拓扑遍历\n",
    "        res=[]\n",
    "        t=1\n",
    "        que=deque()\n",
    "        for i in dic2:\n",
    "            if dic2[i] == 0:\n",
    "                que.append(i)\n",
    "        while len(que):\n",
    "            now=que.popleft()\n",
    "            res.append(now)\n",
    "            if now in dic1:\n",
    "                for j in dic1[now]:\n",
    "                    dic2[j] -= 1\n",
    "                    if dic2[j]==0:\n",
    "                        que.append(j)\n",
    "                        dic2.pop(j)\n",
    "        if len(res)==numCourses:\n",
    "            return res\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        graph = defaultdict(set)\n",
    "        degree = [0]*numCourses\n",
    "        for i in prerequisites:\n",
    "            graph[i[1]].add(i[0])\n",
    "            degree[i[0]]+=1\n",
    "        stack = []\n",
    "        for i in range(numCourses):\n",
    "            if degree[i]==0:\n",
    "                stack.append(i)\n",
    "        ans = []\n",
    "        while stack:\n",
    "            pop = stack.pop()\n",
    "            ans.append(pop)\n",
    "            for ne in graph[pop]:\n",
    "                degree[ne]-=1\n",
    "                if degree[ne]==0:\n",
    "                    stack.append(ne)\n",
    "        if len(ans)<numCourses:\n",
    "            return []\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def findOrder(self, n: int, pres: List[List[int]]) -> List[int]:\n",
    "        G = [set() for _ in range(n)]\n",
    "        IN = [0] * n\n",
    "\n",
    "        for p in pres:\n",
    "            x, y = p[0], p[1]\n",
    "            G[y].add(x)\n",
    "            IN[x] += 1\n",
    "        \n",
    "        q = queue.Queue()\n",
    "        for i in range(n):\n",
    "            if IN[i] == 0:\n",
    "                q.put(i)\n",
    "\n",
    "        ret = []\n",
    "        while q.qsize() > 0:\n",
    "            x = q.get()\n",
    "            ret.append(x)\n",
    "            for y in G[x]:\n",
    "                IN[y] -= 1\n",
    "                if IN[y] == 0:\n",
    "                    q.put(y)\n",
    "\n",
    "        return ret if len(ret) == n else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        d=collections.defaultdict(list)\n",
    "        notStart=collections.defaultdict(list)\n",
    "        for i in prerequisites:\n",
    "            d[i[1]].append(i[0])\n",
    "        \n",
    "        for i in prerequisites:\n",
    "            notStart[i[0]].append(i[1])\n",
    "        \n",
    "        temp=[]\n",
    "        # 加载所有起点\n",
    "        q=collections.deque()\n",
    "        for i in d:\n",
    "            if i not in notStart:\n",
    "                q.append(i)\n",
    "\n",
    "        s=set()\n",
    "\n",
    "        while q:\n",
    "            num=q.popleft()\n",
    "            # 是否满足条件\n",
    "            if num in notStart:\n",
    "                tempS=set(notStart[num])\n",
    "                if tempS&s!=tempS:\n",
    "                    continue\n",
    "            if num in s:\n",
    "                continue\n",
    "            temp.append(num)\n",
    "            s.add(num)\n",
    "            if len(temp)==numCourses:\n",
    "                    return temp\n",
    "            if num in d:\n",
    "                for j in d[num]:\n",
    "                    q.append(j)\n",
    "    \n",
    "        # 补数\n",
    "        for i in range(numCourses):\n",
    "            if i not in s and i not in notStart:\n",
    "                s.add(i)\n",
    "                temp.append(i)\n",
    "            if len(temp)==numCourses:\n",
    "                break\n",
    "\n",
    "        return  temp if len(temp)==numCourses else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "\n",
    "        order = defaultdict(set)\n",
    "        indegree = defaultdict(int)\n",
    "        \n",
    "        for i,j in prerequisites:\n",
    "            order[j].add(i)\n",
    "            indegree[i]+=1\n",
    "        \n",
    "        temp = []\n",
    "        for i in range(numCourses):\n",
    "            if not indegree[i]:\n",
    "                temp.append(i)\n",
    "        res = []\n",
    "        while temp:\n",
    "            node = temp.pop()\n",
    "            res.append(node)\n",
    "            for i in order[node]:\n",
    "                indegree[i]-=1\n",
    "                if not indegree[i]:\n",
    "                    temp.append(i)\n",
    "        \n",
    "        return res if len(res) == numCourses else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        Courses = [i for i in range(numCourses)]\n",
    "        #使用字典来记录每门课程的先修课程情况\n",
    "        cur_Courses = {k:None for k in range(numCourses)}\n",
    "        #已修课程集合\n",
    "        studied = set()\n",
    "        #未修课程集合\n",
    "        non_studied = set(Courses)\n",
    "        #修课顺序\n",
    "        schdule = []\n",
    "        if prerequisites == []:\n",
    "            return Courses\n",
    "        for c in prerequisites:\n",
    "            if cur_Courses[c[0]] != None:\n",
    "                cur_Courses[c[0]].add(c[1])\n",
    "            else:\n",
    "                cur_Courses[c[0]] = {c[1]}\n",
    "        for i in range(numCourses):\n",
    "            if cur_Courses[i] == None:\n",
    "                studied.add(i)\n",
    "                schdule.append(i)\n",
    "        flag = 0\n",
    "        while flag == 0:\n",
    "            for k,v in cur_Courses.items():\n",
    "                if (k not in studied and v.issubset(studied)):\n",
    "                    studied.add(k)\n",
    "                    schdule.append(k)\n",
    "                    if studied == non_studied:  \n",
    "                        return schdule\n",
    "                else:\n",
    "                    continue\n",
    "\n",
    "            for k,v in cur_Courses.items():\n",
    "                if (k not in studied and v.issubset(studied)):\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "        return []\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        dic=dict()\n",
    "        next=set(list(range(numCourses)))\n",
    "        for i in range(numCourses):\n",
    "            dic[i]=[0,set()]\n",
    "        for i in prerequisites:\n",
    "            s=dic[i[1]]\n",
    "            s[1].add(i[0])\n",
    "            dic[i[1]]=s\n",
    "            dic[i[0]][0]+=1\n",
    "            next.discard(i[0])\n",
    "        ans=list(next)\n",
    "        while next!=set():\n",
    "            now=next\n",
    "            next=set()\n",
    "            for i in now:\n",
    "                for j in dic[i][1]:\n",
    "                    dic[j][0]-=1\n",
    "                    if dic[j][0]==0:\n",
    "                        next.add(j)\n",
    "                        ans.append(j)\n",
    "        if len(ans)!=numCourses:\n",
    "            return []\n",
    "        else:\n",
    "            return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        dic = defaultdict(set)\n",
    "        ans,visited = [0]*numCourses,{}\n",
    "        res = []\n",
    "        for f,t in prerequisites:\n",
    "            dic[t].add(f)\n",
    "            ans[f] += 1\n",
    "        print(dic,ans)\n",
    "        queue = deque([u for u in range(numCourses) if ans[u] == 0])\n",
    "        while queue:\n",
    "            key = queue.popleft()\n",
    "            res.append(key)\n",
    "            for u in dic[key]:\n",
    "                ans[u] -= 1\n",
    "                if ans[u] == 0:\n",
    "                    queue.append(u)\n",
    "        if len(res) != numCourses:\n",
    "            return []\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, n: int, p: List[List[int]]) -> List[int]:\n",
    "        a = {i: set() for i in range(n)}\n",
    "        b = {i: set() for i in range(n)}\n",
    "        for x, y in p:\n",
    "            a[x].add(y)\n",
    "            b[y].add(x)\n",
    "        \n",
    "        ans = []\n",
    "        g = [i for i in range(n) if not a[i]]\n",
    "        while g:\n",
    "            x = g.pop(0)\n",
    "            for y in b[x]:\n",
    "                if x in a[y]: a[y].remove(x)\n",
    "                if not a[y]: g.append(y)\n",
    "            ans.append(x)\n",
    "        return ans if len(ans) == n else []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        graph = {node: set() for node in range(numCourses)}\n",
    "        indegree = {node: 0 for node in range(numCourses)}\n",
    "\n",
    "        for node_in, node_out in prerequisites:\n",
    "            graph[node_out].add(node_in)\n",
    "            indegree[node_in] += 1\n",
    "        \n",
    "        queue = collections.deque([node for node in indegree if indegree[node] == 0])\n",
    "        topo_lst = []\n",
    "        num_courses = 0\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            topo_lst.append(node)\n",
    "            num_courses += 1\n",
    "            for neighbor in graph[node]:\n",
    "                indegree[neighbor] -= 1\n",
    "                if indegree[neighbor] == 0:\n",
    "                    queue.append(neighbor)\n",
    "\n",
    "        return topo_lst if num_courses == numCourses else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        dic=dict()\n",
    "        next=set()\n",
    "        c=set()\n",
    "        for i in range(numCourses):\n",
    "            dic[i]=[0,set()]\n",
    "        for i in prerequisites:\n",
    "            s=dic[i[1]]\n",
    "            s[1].add(i[0])\n",
    "            dic[i[1]]=s\n",
    "            dic[i[0]][0]+=1\n",
    "            c.add(i[0])\n",
    "        next=set(list(range(numCourses)))-c\n",
    "        ans=list(next)\n",
    "        while next!=set():\n",
    "            now=next\n",
    "            next=set()\n",
    "            for i in now:\n",
    "                for j in dic[i][1]:\n",
    "                    dic[j][0]-=1\n",
    "                    if dic[j][0]==0:\n",
    "                        next.add(j)\n",
    "                        ans.append(j)\n",
    "        if len(ans)!=numCourses:\n",
    "            return []\n",
    "        else:\n",
    "            return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        dic=dict()\n",
    "        next=set()\n",
    "        c=set()\n",
    "        for i in range(numCourses):\n",
    "            dic[i]=[0,set()]\n",
    "        for i in prerequisites:\n",
    "            s=dic[i[1]]\n",
    "            s[1].add(i[0])\n",
    "            dic[i[1]]=s\n",
    "            dic[i[0]][0]+=1\n",
    "            c.add(i[0])\n",
    "        next=set(list(range(numCourses)))-c\n",
    "        ans=list(next)\n",
    "        while next!=set():\n",
    "            now=next\n",
    "            next=set()\n",
    "            for i in now:\n",
    "                for j in dic[i][1]:\n",
    "                    dic[j][0]-=1\n",
    "                    if dic[j][0]==0:\n",
    "                        next.add(j)\n",
    "                        ans.append(j)\n",
    "        if len(ans)!=numCourses:\n",
    "            return []\n",
    "        else:\n",
    "            return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        dic=dict()\n",
    "        next=set()\n",
    "        c=set()\n",
    "        for i in range(numCourses):\n",
    "            dic[i]=[0,set()]\n",
    "        for i in prerequisites:\n",
    "            s=dic[i[1]]\n",
    "            s[1].add(i[0])\n",
    "            dic[i[1]]=s\n",
    "            dic[i[0]][0]+=1\n",
    "            c.add(i[0])\n",
    "        next=set(list(range(numCourses)))-c\n",
    "        ans=list(next)\n",
    "        while next!=set():\n",
    "            now=next\n",
    "            next=set()\n",
    "            for i in now:\n",
    "                for j in dic[i][1]:\n",
    "                    dic[j][0]-=1\n",
    "                    if dic[j][0]==0:\n",
    "                        next.add(j)\n",
    "                        ans.append(j)\n",
    "        if len(ans)!=numCourses:\n",
    "            return []\n",
    "        else:\n",
    "            return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # 构建领接表结构的graph\n",
    "        self.graph = defaultdict(list)\n",
    "        for crs, pre in prerequisites:\n",
    "            self.graph[crs].append(pre)\n",
    "        \n",
    "        # dfs遍历graph\n",
    "        self.visited, self.onPath = set(), set()\n",
    "        self.hasCycle = False\n",
    "        self.output = []\n",
    "        for c in range(numCourses):\n",
    "            self.dfs(c)\n",
    "\n",
    "        if self.hasCycle: return []\n",
    "        return self.output\n",
    "\n",
    "    def dfs(self, crs):\n",
    "        if crs in self.onPath:\n",
    "            self.hasCycle = True\n",
    "            return \n",
    "        if crs in self.visited: return\n",
    "        \n",
    "        self.visited.add(crs)\n",
    "        self.onPath.add(crs)\n",
    "        for pre in self.graph[crs]:\n",
    "            self.dfs(pre)\n",
    "        self.onPath.remove(crs)\n",
    "        # 后序遍历结果即为拓扑排序\n",
    "        self.output.append(crs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        self.on_path = [False] * numCourses\n",
    "        self.finished = [False] * numCourses\n",
    "        self.plan = defaultdict(list)\n",
    "        self.res = []\n",
    "        for pre, post in prerequisites:\n",
    "            self.plan[pre].append(post)\n",
    "        for i in range(numCourses):\n",
    "            if not self.traverse(i):\n",
    "                return []\n",
    "        return self.res\n",
    "\n",
    "    def traverse(self, i: int) -> bool:\n",
    "        if self.on_path[i]:\n",
    "            return False\n",
    "        if self.finished[i]:\n",
    "            return True\n",
    "        self.on_path[i] = True\n",
    "        self.finished[i] = True\n",
    "        for child in self.plan[i]:\n",
    "            if not self.traverse(child):\n",
    "                return False\n",
    "        self.res.append(i)\n",
    "        self.on_path[i] = False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        nexts=DefaultDict(set) # 建立下一节课的字典\n",
    "        needs=DefaultDict(set) # 建立依赖的字典\n",
    "        for a,b in prerequisites:\n",
    "            nexts[b].add(a)\n",
    "            needs[a].add(b)\n",
    "        # 找到第一节课——没有依赖的课\n",
    "        first_classes=set([i for i in range(numCourses)])\n",
    "        for _,next in nexts.items():\n",
    "            first_classes=first_classes-next\n",
    "        classes=first_classes    # 现有课程（学习顺序）\n",
    "        path=list(first_classes) # 学习路径\n",
    "        queue=deque(path)        # 做bfs\n",
    "        while queue:\n",
    "            class_now=queue.popleft() # 当前课程\n",
    "            classes_next=nexts[class_now] # 下一节可选的课程\n",
    "            for class_next in classes_next: # 某一个课程\n",
    "                if class_next not in classes: # 没学过这节课，可以学\n",
    "                    if needs[class_next].issubset(classes): # 先修课程已学习\n",
    "                        path.append(class_next) # 学习\n",
    "                        classes.add(class_next)\n",
    "                        queue.append(class_next) # 继续学\n",
    "        return path if len(path)==numCourses else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        next_courses = {}\n",
    "        pre_courses = {}\n",
    "        learned_courses = {i for i in range(numCourses)}\n",
    "        for pre in prerequisites:\n",
    "            next_courses.setdefault(pre[1], set()).add(pre[0])\n",
    "            pre_courses.setdefault(pre[0], set()).add(pre[1])\n",
    "            if pre[0] in learned_courses:\n",
    "                learned_courses.remove(pre[0])\n",
    "        res = []\n",
    "        while learned_courses:\n",
    "            res.extend(list(learned_courses))\n",
    "            next_learned_courses = set()\n",
    "            for c in learned_courses:\n",
    "                if c not in next_courses:\n",
    "                    continue\n",
    "                for n_course in next_courses[c]:\n",
    "                    p_courses = pre_courses[n_course]\n",
    "                    p_courses.remove(c)\n",
    "                    if not p_courses:\n",
    "                        next_learned_courses.add(n_course)\n",
    "            learned_courses = next_learned_courses\n",
    "        return res if len(res) == numCourses else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        pre_course=[[] for i in range(numCourses)]\n",
    "        res=[]\n",
    "        for a, b in prerequisites:\n",
    "            pre_course[a].append(b)\n",
    "        visited=[0 for i in range(numCourses)]\n",
    "        def traverse(v):\n",
    "            if on_path[v]:\n",
    "                return False\n",
    "            if visited[v]:\n",
    "                return True\n",
    "            on_path[v]=1\n",
    "            visited[v]=1\n",
    "            for c in pre_course[v]:\n",
    "                if not traverse(c):\n",
    "                    return False\n",
    "            on_path[v]=0\n",
    "            res.append(v)\n",
    "            return True\n",
    "        for i in range(numCourses):\n",
    "            on_path=[0 for i in range(numCourses)]\n",
    "            if not traverse(i):\n",
    "                return []\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # 存储有向图\n",
    "        edges = collections.defaultdict(list)\n",
    "        # 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成\n",
    "        visited = [0] * numCourses\n",
    "        # 用数组来模拟栈，下标 0 为栈底，n-1 为栈顶\n",
    "        result = list()\n",
    "        # 判断有向图中是否有环\n",
    "        valid = True\n",
    "\n",
    "        for info in prerequisites:\n",
    "            edges[info[1]].append(info[0])\n",
    "        print(edges)\n",
    "\n",
    "\n",
    "        choose = set(i for i in range(numCourses))\n",
    "        track = []\n",
    "\n",
    "        self.res = []\n",
    "        def dfs(v, track):\n",
    "            if len(track)==numCourses:\n",
    "                self.res .append(track[:])\n",
    "                return None   \n",
    "            if len(choose)==0:\n",
    "                return None \n",
    "            for v_ in graph[v]:\n",
    "                choose.remove(v_)\n",
    "                dfs(choose, track+[v])\n",
    "                choose.append(v_)\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # graph = {}\n",
    "        # for pre in prerequisites:\n",
    "        #     v, p = pre[0], pre[1]\n",
    "        #     if v not in graph:\n",
    "        #         graph[v] = set()\n",
    "        #         graph[v].add(p)\n",
    "        #     else:\n",
    "        #         graph[v].add(p)\n",
    "\n",
    "        # def dfs(choose, track, set_track):\n",
    "        #     if len(self.res)>0:\n",
    "        #         return None\n",
    "        #     if len(track)==numCourses:\n",
    "        #         self.res.append(track[:])\n",
    "        #         return None \n",
    "        #     for p in choose:\n",
    "        #         if p in graph:\n",
    "        #             pre_ = graph[p]\n",
    "        #             if p not in set_track and (not pre_ & set_track):\n",
    "        #                 choose.remove(p)\n",
    "        #                 track.append(p)\n",
    "        #                 set_track.add(p)\n",
    "        #                 dfs(choose, track, set_track)\n",
    "        #                 choose.add(p)\n",
    "        #                 track.pop()\n",
    "        #                 set_track.remove(p)\n",
    "        #         else:\n",
    "        #             if p not in set_track:\n",
    "        #                 choose.remove(p)\n",
    "        #                 track.append(p)\n",
    "        #                 set_track.add(p)\n",
    "        #                 dfs(choose, track, set_track)\n",
    "        #                 choose.add(p)\n",
    "        #                 track.pop()\n",
    "        #                 set_track.remove(p)\n",
    "\n",
    "\n",
    "        # self.res = []\n",
    "        # choose = set([i for i in range(numCourses)])\n",
    "        # dfs(choose, [], set())\n",
    "        # if len(self.res)==0:\n",
    "        #     return []\n",
    "        # return self.res[0][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        degrees = defaultdict(set)\n",
    "        out_degrees = defaultdict(set)\n",
    "        for a, b in prerequisites: \n",
    "            degrees[a].add(b)\n",
    "            out_degrees[b].add(a)\n",
    "\n",
    "\n",
    "        que = [i for i in range(numCourses) if not degrees[i]]\n",
    "        ans = []\n",
    "        while que:\n",
    "            cur = que[0]\n",
    "            que = que[1:]\n",
    "            ans.append(cur)\n",
    "\n",
    "            for nxt in out_degrees[cur]:\n",
    "                degrees[nxt].remove(cur)\n",
    "                if not degrees[nxt]:\n",
    "                    que.append(nxt)\n",
    "        \n",
    "        if len(ans) != numCourses:\n",
    "            return []\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        def bulid_graph():\n",
    "            graph=[[] for _ in range(numCourses)]\n",
    "            for pair in prerequisites:\n",
    "                from_,to_=pair[1],pair[0]\n",
    "                graph[from_].append(to_)\n",
    "            return graph\n",
    "        global has_circle\n",
    "        has_circle=False\n",
    "        graph=bulid_graph()\n",
    "        visited=[False]*numCourses\n",
    "        path=[False]*numCourses\n",
    "        res=[]\n",
    "        def traverse(node):\n",
    "            global has_circle\n",
    "            # print(path)\n",
    "            if path[node]:\n",
    "                has_circle=True\n",
    "            if has_circle or visited[node]:\n",
    "                return\n",
    "            visited[node]=True\n",
    "            path[node]=True\n",
    "            for i in graph[node]:\n",
    "                traverse(i)\n",
    "            res.append(node)\n",
    "            path[node]=False\n",
    "        for i in range(numCourses):\n",
    "            traverse(i)\n",
    "        # print(res)\n",
    "        if has_circle:\n",
    "            return []\n",
    "        res.reverse()\n",
    "        return  res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        course_dict = defaultdict(set)\n",
    "        course_dict_2 = defaultdict(set)\n",
    "\n",
    "        course_not_study = set()\n",
    "        for p in prerequisites:\n",
    "            course_dict[p[1]].add(p[0])\n",
    "            course_dict_2[p[0]].add(p[1])\n",
    "            course_not_study.add(p[0])\n",
    "        visited = []\n",
    "        q = []\n",
    "        for i in range(numCourses):\n",
    "            if i not in course_not_study:\n",
    "                q.append(i)\n",
    "        res = q\n",
    "        while q:\n",
    "            new_q = []\n",
    "\n",
    "            for item in q:\n",
    "                for child in course_dict[item]:\n",
    "                    if child not in res:\n",
    "                        if course_dict_2[child] & set(res) == course_dict_2[child]:\n",
    "                            new_q.append(child)\n",
    "                            res.append(child)\n",
    "\n",
    "            q = new_q\n",
    "\n",
    "        if len(res) == numCourses:\n",
    "            return res\n",
    "\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import graphlib\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        d = {i:set() for i in range(numCourses)}\n",
    "        for i in prerequisites: d[i[0]].add(i[1])\n",
    "        ts = graphlib.TopologicalSorter(d)\n",
    "        try: return list(ts.static_order())\n",
    "        except: return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # 判断课程顺序以及有前置课程的课\n",
    "        foward, backward = dict(), dict()\n",
    "        for prerequisity in prerequisites:\n",
    "            front, rear = prerequisity[1], prerequisity[0]\n",
    "            if front in foward:\n",
    "                foward[front].add(rear)\n",
    "            else:\n",
    "                foward[front] = set([rear])\n",
    "            if rear in backward:\n",
    "                backward[rear].add(front)\n",
    "            else:\n",
    "                backward[rear] = set([front])\n",
    "        # 选出没有前置课程的课\n",
    "        crs_openset = list()\n",
    "        for crs_index in range(numCourses):\n",
    "            # 判断是否有前置课程\n",
    "            if crs_index in backward:\n",
    "                continue\n",
    "            crs_openset.append(crs_index)\n",
    "        # 进行广度优先搜索\n",
    "        res = list()\n",
    "        while crs_openset:\n",
    "            cur_crs_index = crs_openset.pop(0)\n",
    "            # 判断当前课程是否可以上\n",
    "            is_ready = True\n",
    "            if cur_crs_index in backward:\n",
    "                for front_crs_index in backward[cur_crs_index]:\n",
    "                    if not front_crs_index in res:\n",
    "                        is_ready = False\n",
    "                        break\n",
    "            if not is_ready:\n",
    "                continue\n",
    "            if not cur_crs_index in res:\n",
    "                res.append(cur_crs_index)\n",
    "            if cur_crs_index in foward:\n",
    "                for next_crs_index in foward[cur_crs_index]:\n",
    "                    crs_openset.append(next_crs_index)\n",
    "        print(res)\n",
    "        if len(res) == numCourses:\n",
    "            return res\n",
    "        else:\n",
    "            return list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        course_dict = defaultdict(set)\n",
    "        course_dict_2 = defaultdict(set)\n",
    "\n",
    "        course_not_study = set()\n",
    "        for p in prerequisites:\n",
    "            course_dict[p[1]].add(p[0])\n",
    "            course_dict_2[p[0]].add(p[1])\n",
    "            course_not_study.add(p[0])\n",
    "        visited = []\n",
    "        q = []\n",
    "        for i in range(numCourses):\n",
    "            if i not in course_not_study:\n",
    "                q.append(i)\n",
    "        res = q\n",
    "        while q:\n",
    "            new_q = []\n",
    "\n",
    "            for item in q:\n",
    "                for child in course_dict[item]:\n",
    "                    if child not in res:\n",
    "                        if course_dict_2[child] & set(res) == course_dict_2[child]:\n",
    "                            new_q.append(child)\n",
    "                            res.append(child)\n",
    "\n",
    "            q = new_q\n",
    "\n",
    "        if len(res) == numCourses:\n",
    "            return res\n",
    "\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        course_dict = defaultdict(set)\n",
    "        course_dict_2 = defaultdict(set)\n",
    "\n",
    "        course_not_study = set()\n",
    "        for p in prerequisites:\n",
    "            course_dict[p[1]].add(p[0])\n",
    "            course_dict_2[p[0]].add(p[1])\n",
    "            course_not_study.add(p[0])\n",
    "        visited = []\n",
    "        q = []\n",
    "        for i in range(numCourses):\n",
    "            if i not in course_not_study:\n",
    "                q.append(i)\n",
    "        res = q\n",
    "        while q:\n",
    "            new_q = []\n",
    "\n",
    "            for item in q:\n",
    "                for child in course_dict[item]:\n",
    "                    if child not in res:\n",
    "                        if course_dict_2[child] & set(res) == course_dict_2[child]:\n",
    "                            new_q.append(child)\n",
    "                            res.append(child)\n",
    "\n",
    "            q = new_q\n",
    "\n",
    "        if len(res) == numCourses:\n",
    "            return res\n",
    "\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        needs = [0]*numCourses\n",
    "        unlock = defaultdict(list)\n",
    "        for nxt,pre in prerequisites:\n",
    "            needs[nxt] += 1\n",
    "            unlock[pre].append(nxt)\n",
    "        q = deque(idx for idx,val in enumerate(needs) if val == 0)\n",
    "        res = []\n",
    "        print(unlock)\n",
    "        while q:\n",
    "            p = q.popleft()\n",
    "            res.append(p)\n",
    "            for i in unlock[p]:\n",
    "                needs[i] -= 1\n",
    "                if needs[i] == 0: q.append(i)\n",
    "            print(res,p,q)\n",
    "        if len(res) < numCourses: return []\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # 存储有向图\n",
    "        \n",
    "        edges = collections.defaultdict(list)\n",
    "        # 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成\n",
    "        visited = [0] * numCourses\n",
    "        # 用数组来模拟栈，下标 0 为栈底，n-1 为栈顶\n",
    "        result = list()\n",
    "        # 判断有向图中是否有环\n",
    "        valid = True\n",
    "\n",
    "        for info in prerequisites:\n",
    "            edges[info[1]].append(info[0])\n",
    "        \n",
    "        def dfs(u: int):\n",
    "            nonlocal valid\n",
    "            # 将节点标记为「搜索中」\n",
    "            visited[u] = 1\n",
    "            # 搜索其相邻节点\n",
    "            # 只要发现有环，立刻停止搜索\n",
    "            for v in edges[u]:\n",
    "                # 如果「未搜索」那么搜索相邻节点\n",
    "                if visited[v] == 0:\n",
    "                    dfs(v)\n",
    "                    if not valid:\n",
    "                        return\n",
    "                # 如果「搜索中」说明找到了环\n",
    "                elif visited[v] == 1:\n",
    "                    valid = False\n",
    "                    return\n",
    "            # 将节点标记为「已完成」\n",
    "            visited[u] = 2\n",
    "            # 将节点入栈\n",
    "            result.append(u)\n",
    "        \n",
    "        # 每次挑选一个「未搜索」的节点，开始进行深度优先搜索\n",
    "        for i in range(numCourses):\n",
    "            if valid and not visited[i]:\n",
    "                dfs(i)\n",
    "        \n",
    "        if not valid:\n",
    "            return list()\n",
    "        \n",
    "        # 如果没有环，那么就有拓扑排序\n",
    "        # 注意下标 0 为栈底，因此需要将数组反序输出\n",
    "        return result[::-1]\n",
    "        '''\n",
    "        edges = defaultdict(list)\n",
    "        visited = [0]*numCourses\n",
    "        valid = True\n",
    "        res = []\n",
    "        for item in prerequisites:\n",
    "            edges[item[1]] = prerequisites[item[0]]\n",
    "        dfs(u):\n",
    "            nonlocal valid\n",
    "            visited[u] = 1\n",
    "            for v in edges[u]:\n",
    "                if visited[v]==0:\n",
    "                    dfs(v)\n",
    "                    if not valid:\n",
    "                        return\n",
    "                elif visited[v] == 1:\n",
    "                    valid = False\n",
    "                    return\n",
    "                visited[u]=2\n",
    "                res.append(u)\n",
    "\n",
    "                \n",
    "        for i in range(numCourses):\n",
    "            if valid and not visited[i]:\n",
    "                dfs(i)'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        course_dict = defaultdict(set)\n",
    "        course_dict_2 = defaultdict(set)\n",
    "\n",
    "        course_not_study = set()\n",
    "        for p in prerequisites:\n",
    "            course_dict[p[1]].add(p[0])\n",
    "            course_dict_2[p[0]].add(p[1])\n",
    "            course_not_study.add(p[0])\n",
    "        visited = []\n",
    "        q = []\n",
    "        for i in range(numCourses):\n",
    "            if i not in course_not_study:\n",
    "                q.append(i)\n",
    "        res = q\n",
    "        while q:\n",
    "            new_q = []\n",
    "\n",
    "            for item in q:\n",
    "                for child in course_dict[item]:\n",
    "                    if child not in res:\n",
    "                        if course_dict_2[child] & set(res) == course_dict_2[child]:\n",
    "                            new_q.append(child)\n",
    "                            res.append(child)\n",
    "\n",
    "            q = new_q\n",
    "\n",
    "        if len(res) == numCourses:\n",
    "            return res\n",
    "\n",
    "        return []\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        from collections import defaultdict\n",
    "        graph = defaultdict(list)\n",
    "        for x, y in prerequisites:\n",
    "            graph[y].append(x)\n",
    "        res = []\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(i, being_visited):\n",
    "            if i in being_visited:\n",
    "                return False\n",
    "            if i in visited:\n",
    "                return True\n",
    "            visited.add(i)\n",
    "            being_visited.add(i)\n",
    "            for j in graph[i]:\n",
    "                if not dfs(j, being_visited):\n",
    "                    return False\n",
    "            being_visited.remove(i)\n",
    "            res.append(i)\n",
    "            return True\n",
    "        for i in range(numCourses):\n",
    "            if not dfs(i, set()):\n",
    "                return []\n",
    "        return res[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # dfs 后序\n",
    "        graph = {}\n",
    "        for i in range(numCourses):\n",
    "            graph[i] = set()\n",
    "        for a, b in prerequisites:\n",
    "            if a not in graph[b]:\n",
    "                graph[b].add(a)\n",
    "        \n",
    "        onPath = [0 for i in range(numCourses)]\n",
    "        visited = [0 for i in range(numCourses)]\n",
    "        postorder = []\n",
    "        self.hasCycle = False \n",
    "        def dfs(i):\n",
    "            if onPath[i]==1:\n",
    "                self.hasCycle = True\n",
    "                return None\n",
    "            if self.hasCycle == True:\n",
    "                return None \n",
    "            if visited[i] ==1:\n",
    "                return None \n",
    "            onPath[i] = 1\n",
    "            for j in graph[i]:\n",
    "                dfs(j)\n",
    "            onPath[i] = 0\n",
    "            visited[i] = 1\n",
    "            postorder.append(i)\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            dfs(i)\n",
    "        if self.hasCycle:\n",
    "            return []\n",
    "        return postorder[::-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # # dfs 前序，不可以，因为 有的时候并不是遍历过的就不能再被指向。跟后序的路径依赖记录还是有区别。比如，根左右是前序，左已经遍历过，但是右的节点有的也可以指向左，这时前序就会认为有Cycle环，但onpath不会有这个问题。\n",
    "        # graph = {}\n",
    "        # for i in range(numCourses):\n",
    "        #     graph[i] = set()\n",
    "        # for a, b in prerequisites:\n",
    "        #     if a not in graph[b]:\n",
    "        #         graph[b].add(a)\n",
    "        \n",
    "        # preorder = [0 for i in range(numCourses)]\n",
    "        # self.hasCycle = False \n",
    "        # def dfs(i):\n",
    "        #     # if preorder[i]==1:\n",
    "        #     #     self.hasCycle = True\n",
    "        #     #     return None,\n",
    "        #     if self.hasCycle == True:\n",
    "        #         return None \n",
    "        #     preorder[i] = 1\n",
    "        #     for j in graph[i]:\n",
    "        #         if preorder[j]==1:\n",
    "        #             self.hasCycle = True\n",
    "        #             return None \n",
    "        #         dfs(j)\n",
    "\n",
    "        # for i in range(numCourses):\n",
    "        #     if i not in preorder:\n",
    "        #         dfs(i)\n",
    "        # if self.hasCycle:\n",
    "        #     return []\n",
    "        # return preorder \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # def dfs(choose, track, set_track):\n",
    "        #     if len(self.res)>0:\n",
    "        #         return None\n",
    "        #     if len(track)==numCourses:\n",
    "        #         self.res.append(track[:])\n",
    "        #         return None \n",
    "        #     for p in choose:\n",
    "        #         if p in graph:\n",
    "        #             pre_ = graph[p]\n",
    "        #             if p not in set_track and (not pre_&set_track):\n",
    "        #                 choose.remove(p)\n",
    "        #                 track.append(p)\n",
    "        #                 set_track.add(p)\n",
    "        #                 dfs(choose, track, set_track)\n",
    "        #                 choose.add(p)\n",
    "        #                 track.pop()\n",
    "        #                 set_track.remove(p)\n",
    "        #         else:\n",
    "        #             if p not in set_track:\n",
    "        #                 choose.remove(p)\n",
    "        #                 track.append(p)\n",
    "        #                 set_track.add(p)\n",
    "        #                 dfs(choose, track, set_track)\n",
    "        #                 choose.add(p)\n",
    "        #                 track.pop()\n",
    "        #                 set_track.remove(p)\n",
    "\n",
    "\n",
    "        # self.res = []\n",
    "        # choose = set([i for i in range(numCourses)])\n",
    "        # dfs(choose, [], set())\n",
    "        # if len(self.res)==0:\n",
    "        #     return []\n",
    "        # return self.res[0][::-1]\n",
    "        # # return []\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # graph = {}\n",
    "        # for i in range(numCourses):\n",
    "        #     graph[i] = [set(), 0]\n",
    "        # for a, b in prerequisites:\n",
    "        #     if b not in graph[a][0]:\n",
    "        #         graph[a][0].add(b)\n",
    "        #         graph[a][1] +=1\n",
    "\n",
    "        # q = []\n",
    "        # for k in list(graph.keys()):\n",
    "        #     if graph[k][1]==0:\n",
    "        #         q.append(k)\n",
    "        #         graph.pop(k)\n",
    "        # res = [] \n",
    "        # while q:\n",
    "        #     for _ in range(len(q)):\n",
    "        #         v = q.pop()\n",
    "        #         res.append(v)\n",
    "        #         for k in list(graph.keys()):\n",
    "        #             if v in graph[k][0]:\n",
    "        #                 graph[k][0].remove(v)\n",
    "        #                 graph[k][1] -=1\n",
    "        #                 if graph[k][1]==0:\n",
    "        #                     graph.pop(k)\n",
    "        #                     q.append(k)\n",
    "        # if len(res) != numCourses:\n",
    "        #     return []\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "\n",
    "        # dfs\n",
    "        graph = {}\n",
    "        for i in range(numCourses):\n",
    "            graph[i] = set()\n",
    "        for a, b in prerequisites:\n",
    "            if a not in graph[b]:\n",
    "                graph[b].add(a)\n",
    "        \n",
    "        onPath = [0 for i in range(numCourses)]\n",
    "        visited = [0 for i in range(numCourses)]\n",
    "        postorder = []\n",
    "        self.hasCycle = False \n",
    "        def dfs(i):\n",
    "            if onPath[i]==1:\n",
    "                self.hasCycle = True\n",
    "                return None\n",
    "            if self.hasCycle == True :\n",
    "                return None \n",
    "            if visited[i] ==1:\n",
    "                return None \n",
    "            onPath[i] = 1\n",
    "            for j in graph[i]:\n",
    "                dfs(j)\n",
    "            onPath[i] = 0\n",
    "            visited[i] = 1\n",
    "            postorder.append(i)\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            dfs(i)\n",
    "        if self.hasCycle:\n",
    "            return []\n",
    "        return postorder[::-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            dfs(i)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # graph = {}\n",
    "        # for i in range(numCourses):\n",
    "        #     graph[i] = [set(), 0]\n",
    "        # for a, b in prerequisites:\n",
    "        #     if b not in graph[a][0]:\n",
    "        #         graph[a][0].add(b)\n",
    "        #         graph[a][1] +=1\n",
    "\n",
    "        # q = []\n",
    "        # for k in list(graph.keys()):\n",
    "        #     if graph[k][1]==0:\n",
    "        #         q.append(k)\n",
    "        #         graph.pop(k)\n",
    "        # res = [] \n",
    "        # while q:\n",
    "        #     for _ in range(len(q)):\n",
    "        #         v = q.pop()\n",
    "        #         res.append(v)\n",
    "        #         for k in list(graph.keys()):\n",
    "        #             if v in graph[k][0]:\n",
    "        #                 graph[k][0].remove(v)\n",
    "        #                 graph[k][1] -=1\n",
    "        #                 if graph[k][1]==0:\n",
    "        #                     graph.pop(k)\n",
    "        #                     q.append(k)\n",
    "        # if len(res) != numCourses:\n",
    "        #     return []\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "\n",
    "        # dfs\n",
    "        graph = {}\n",
    "        for i in range(numCourses):\n",
    "            graph[i] = set()\n",
    "        for a, b in prerequisites:\n",
    "            if a not in graph[b]:\n",
    "                graph[b].add(a)\n",
    "        \n",
    "        onPath = [0 for i in range(numCourses)]\n",
    "        visited = [0 for i in range(numCourses)]\n",
    "        postorder = []\n",
    "        self.hasCycle = False \n",
    "        def dfs(i):\n",
    "            if onPath[i]==1:\n",
    "                self.hasCycle = True\n",
    "                return None\n",
    "            if self.hasCycle == True :\n",
    "                return None \n",
    "            if visited[i] ==1:\n",
    "                return None \n",
    "            onPath[i] = 1\n",
    "            for j in graph[i]:\n",
    "                dfs(j)\n",
    "            onPath[i] = 0\n",
    "            visited[i] = 1\n",
    "            postorder.append(i)\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            dfs(i)\n",
    "        if self.hasCycle:\n",
    "            return []\n",
    "        return postorder[::-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            dfs(i)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # graph = {}\n",
    "        # for i in range(numCourses):\n",
    "        #     graph[i] = [set(), 0]\n",
    "        # for a, b in prerequisites:\n",
    "        #     if b not in graph[a][0]:\n",
    "        #         graph[a][0].add(b)\n",
    "        #         graph[a][1] +=1\n",
    "\n",
    "        # q = []\n",
    "        # for k in list(graph.keys()):\n",
    "        #     if graph[k][1]==0:\n",
    "        #         q.append(k)\n",
    "        #         graph.pop(k)\n",
    "        # res = [] \n",
    "        # while q:\n",
    "        #     for _ in range(len(q)):\n",
    "        #         v = q.pop()\n",
    "        #         res.append(v)\n",
    "        #         for k in list(graph.keys()):\n",
    "        #             if v in graph[k][0]:\n",
    "        #                 graph[k][0].remove(v)\n",
    "        #                 graph[k][1] -=1\n",
    "        #                 if graph[k][1]==0:\n",
    "        #                     graph.pop(k)\n",
    "        #                     q.append(k)\n",
    "        # if len(res) != numCourses:\n",
    "        #     return []\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # dfs 后序\n",
    "        graph = {}\n",
    "        for i in range(numCourses):\n",
    "            graph[i] = set()\n",
    "        for a, b in prerequisites:\n",
    "            if a not in graph[b]:\n",
    "                graph[b].add(a)\n",
    "        \n",
    "        onPath = [0 for i in range(numCourses)]\n",
    "        visited = [0 for i in range(numCourses)]\n",
    "        postorder = []\n",
    "        self.hasCycle = False \n",
    "        def dfs(i):\n",
    "            if onPath[i]==1:\n",
    "                self.hasCycle = True\n",
    "                return None\n",
    "            if self.hasCycle == True:\n",
    "                return None \n",
    "            if visited[i] ==1:\n",
    "                return None \n",
    "            onPath[i] = 1\n",
    "            for j in graph[i]:\n",
    "                dfs(j)\n",
    "            onPath[i] = 0\n",
    "            visited[i] = 1\n",
    "            postorder.append(i)\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            dfs(i)\n",
    "        if self.hasCycle:\n",
    "            return []\n",
    "        return postorder[::-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # # dfs 前序，不可以，因为 有的时候并不是遍历过的就不能再被指向。跟后序的路径依赖记录还是有区别。比如，根左右是前序，左已经遍历过，但是右的节点有的也可以指向左，这时前序就会认为有Cycle环，但onpath不会有这个问题。\n",
    "        # graph = {}\n",
    "        # for i in range(numCourses):\n",
    "        #     graph[i] = set()\n",
    "        # for a, b in prerequisites:\n",
    "        #     if a not in graph[b]:\n",
    "        #         graph[b].add(a)\n",
    "        \n",
    "        # preorder = [0 for i in range(numCourses)]\n",
    "        # self.hasCycle = False \n",
    "        # def dfs(i):\n",
    "        #     # if preorder[i]==1:\n",
    "        #     #     self.hasCycle = True\n",
    "        #     #     return None,\n",
    "        #     if self.hasCycle == True:\n",
    "        #         return None \n",
    "        #     preorder[i] = 1\n",
    "        #     for j in graph[i]:\n",
    "        #         if preorder[j]==1:\n",
    "        #             self.hasCycle = True\n",
    "        #             return None \n",
    "        #         dfs(j)\n",
    "\n",
    "        # for i in range(numCourses):\n",
    "        #     if i not in preorder:\n",
    "        #         dfs(i)\n",
    "        # if self.hasCycle:\n",
    "        #     return []\n",
    "        # return preorder \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # def dfs(choose, track, set_track):\n",
    "        #     if len(self.res)>0:\n",
    "        #         return None\n",
    "        #     if len(track)==numCourses:\n",
    "        #         self.res.append(track[:])\n",
    "        #         return None \n",
    "        #     for p in choose:\n",
    "        #         if p in graph:\n",
    "        #             pre_ = graph[p]\n",
    "        #             if p not in set_track and (not pre_&set_track):\n",
    "        #                 choose.remove(p)\n",
    "        #                 track.append(p)\n",
    "        #                 set_track.add(p)\n",
    "        #                 dfs(choose, track, set_track)\n",
    "        #                 choose.add(p)\n",
    "        #                 track.pop()\n",
    "        #                 set_track.remove(p)\n",
    "        #         else:\n",
    "        #             if p not in set_track:\n",
    "        #                 choose.remove(p)\n",
    "        #                 track.append(p)\n",
    "        #                 set_track.add(p)\n",
    "        #                 dfs(choose, track, set_track)\n",
    "        #                 choose.add(p)\n",
    "        #                 track.pop()\n",
    "        #                 set_track.remove(p)\n",
    "\n",
    "\n",
    "        # self.res = []\n",
    "        # choose = set([i for i in range(numCourses)])\n",
    "        # dfs(choose, [], set())\n",
    "        # if len(self.res)==0:\n",
    "        #     return []\n",
    "        # return self.res[0][::-1]\n",
    "        # # return []\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # graph = {}\n",
    "        # for i in range(numCourses):\n",
    "        #     graph[i] = [set(), 0]\n",
    "        # for a, b in prerequisites:\n",
    "        #     if b not in graph[a][0]:\n",
    "        #         graph[a][0].add(b)\n",
    "        #         graph[a][1] +=1\n",
    "\n",
    "        # q = []\n",
    "        # for k in list(graph.keys()):\n",
    "        #     if graph[k][1]==0:\n",
    "        #         q.append(k)\n",
    "        #         graph.pop(k)\n",
    "        # res = [] \n",
    "        # while q:\n",
    "        #     for _ in range(len(q)):\n",
    "        #         v = q.pop()\n",
    "        #         res.append(v)\n",
    "        #         for k in list(graph.keys()):\n",
    "        #             if v in graph[k][0]:\n",
    "        #                 graph[k][0].remove(v)\n",
    "        #                 graph[k][1] -=1\n",
    "        #                 if graph[k][1]==0:\n",
    "        #                     graph.pop(k)\n",
    "        #                     q.append(k)\n",
    "        # if len(res) != numCourses:\n",
    "        #     return []\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        graph = {}\n",
    "        for i in range(numCourses):\n",
    "            graph[i] = set()\n",
    "        for c, p in prerequisites:\n",
    "            graph[p].add(c)\n",
    "        \n",
    "        visited = set()\n",
    "        in_queue = set()\n",
    "        post_re_order = []\n",
    "\n",
    "        def dfs(c):\n",
    "            \"\"\"return has_cycle\"\"\"\n",
    "            visited.add(c)\n",
    "            in_queue.add(c)\n",
    "            for nb in graph[c]:\n",
    "                if nb in in_queue: return True\n",
    "                if nb not in visited:\n",
    "                    if dfs(nb): return True\n",
    "            in_queue.remove(c)\n",
    "            post_re_order.append(c)\n",
    "            return False\n",
    "\n",
    "        \n",
    "        for course in range(numCourses):\n",
    "            if course not in visited:\n",
    "                if dfs(course): return []\n",
    "        \n",
    "        return post_re_order[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        pre = {}\n",
    "        degree1 = set()\n",
    "        for i in range(numCourses):\n",
    "            pre[i] = set()\n",
    "        for p0, p1 in prerequisites:\n",
    "            pre[p1].add(p0)\n",
    "            degree1.add(p0)\n",
    "        ans = []\n",
    "        seen = set()\n",
    "        def dfs(i):\n",
    "            if i in seen:\n",
    "                return False\n",
    "            else:\n",
    "                seen.add(i)\n",
    "                for next_i in pre[i]:\n",
    "                    ret = dfs(next_i)\n",
    "                    if not ret:\n",
    "                        return False\n",
    "                seen.remove(i)\n",
    "                if i not in ans:\n",
    "                    ans.append(i)\n",
    "                return True\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            if i not in degree1:\n",
    "                if not dfs(i):\n",
    "                    return []\n",
    "        return ans[::-1] if len(ans) == numCourses else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        graph = self.buildGraph(numCourses, prerequisites)\n",
    "        self.visited = [False] * numCourses\n",
    "        self.onPath = [False] * numCourses\n",
    "         # 记录是否存在环\n",
    "        self.hasCycle = False\n",
    "        # 记录后序遍历结果\n",
    "        self.postorder = []\n",
    "        for i in range(numCourses):\n",
    "            self.traverse(graph, i)\n",
    "        if self.hasCycle:\n",
    "            return []\n",
    "        self.postorder.reverse()\n",
    "        return self.postorder\n",
    "    \n",
    "    def traverse(self, graph, s):\n",
    "        if self.onPath[s] == True:\n",
    "            self.hasCycle = True\n",
    "        if self.visited[s] or self.hasCycle:\n",
    "            return \n",
    "        self.visited[s] = True\n",
    "        self.onPath[s] = True\n",
    "        for t in graph[s]:\n",
    "            self.traverse(graph, t)\n",
    "        self.postorder.append(s)\n",
    "        self.onPath[s] = False\n",
    "    \n",
    "    def buildGraph(self, numCourses, prerequisites):\n",
    "        graph = [[] for _ in range(numCourses)]\n",
    "        for to_, form_ in prerequisites:\n",
    "            graph[form_].append(to_)\n",
    "        return graph\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        graph = self.buildGraph(numCourses, prerequisites)\n",
    "        self.visited = [False] * numCourses\n",
    "        self.onPath = [False] * numCourses\n",
    "         # 记录是否存在环\n",
    "        self.hasCycle = False\n",
    "        # 记录后序遍历结果\n",
    "        self.postorder = []\n",
    "        for i in range(numCourses):\n",
    "            self.traverse(graph, i)\n",
    "        if self.hasCycle:\n",
    "            return []\n",
    "        self.postorder.reverse()\n",
    "        return self.postorder\n",
    "    \n",
    "    def traverse(self, graph, s):\n",
    "        if self.onPath[s] == True:\n",
    "            self.hasCycle = True\n",
    "        if self.visited[s] or self.hasCycle:\n",
    "            return \n",
    "        self.visited[s] = True\n",
    "        self.onPath[s] = True\n",
    "        for t in graph[s]:\n",
    "            self.traverse(graph, t)\n",
    "        self.postorder.append(s)\n",
    "        self.onPath[s] = False\n",
    "    \n",
    "    def buildGraph(self, numCourses, prerequisites):\n",
    "        graph = [[] for _ in range(numCourses)]\n",
    "        for to_, form_ in prerequisites:\n",
    "            graph[form_].append(to_)\n",
    "        return graph\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        def dfs(i, adjacency, flags):\n",
    "            if flags[i] == -1: return True\n",
    "            if flags[i] == 1: return False\n",
    "            flags[i] = 1\n",
    "            for j in adjacency[i]:\n",
    "                if not dfs(j, adjacency, flags): return False\n",
    "            flags[i] = -1\n",
    "            res.append(i)\n",
    "            return True\n",
    "        res = []\n",
    "        adjacency = [[] for _ in range(numCourses)]\n",
    "        flags = [0] * numCourses\n",
    "        for cur, pre in prerequisites:\n",
    "            adjacency[pre].append(cur)\n",
    "        for i in range(numCourses):\n",
    "            if not dfs(i, adjacency, flags): return []\n",
    "        return res[::-1]\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.onpath = []\n",
    "        self.hascycle = False\n",
    "        self.visited = []\n",
    "        self.track = []\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        self.onpath = [False for i in range(numCourses)]\n",
    "        self.visited = [False for i in range(numCourses)]\n",
    "        graph = self.buildgraph(numCourses,prerequisites)\n",
    "        for i in range(numCourses):\n",
    "            self.traverse(graph,i)\n",
    "        if self.hascycle:\n",
    "            return []\n",
    "        self.track.reverse()\n",
    "        return self.track\n",
    "    def traverse(self,graph,index):\n",
    "        if self.onpath[index]:\n",
    "            self.hascycle = True\n",
    "        if self.visited[index] or self.hascycle:\n",
    "            return None\n",
    "        self.onpath[index]=True\n",
    "        self.visited[index] = True\n",
    "\n",
    "        for item in graph[index]:\n",
    "            self.traverse(graph,item)\n",
    "        self.track.append(index) #先将最底层的课程添加到数组中\n",
    "        self.onpath[index]=False\n",
    "\n",
    "\n",
    "    def buildgraph(self,numCourses,prerequisites):\n",
    "        graph = [[]for i in range(numCourses)]\n",
    "        for item in prerequisites:\n",
    "            from_,to_ = item[1],item[0]\n",
    "            graph[from_].append(to_)\n",
    "        return graph\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # 记录后序遍历结果\n",
    "        self.postorder = []\n",
    "        # 记录是否存在环\n",
    "        self.hasCycle = [False]\n",
    "        self.visited = [False] * numCourses\n",
    "        self.onPath = [False] * numCourses\n",
    "\n",
    "        self.graph = self.buildGraph(numCourses, prerequisites)\n",
    "        # 遍历图\n",
    "        for i in range(numCourses):\n",
    "            self.traverse(self.graph, i)\n",
    "        # 有环图无法进行拓扑排序\n",
    "        if self.hasCycle[0]:\n",
    "            return []\n",
    "        # 逆后序遍历结果即为拓扑排序结果\n",
    "        self.postorder.reverse()\n",
    "        res = []\n",
    "        for i in self.postorder:\n",
    "            res.append(i)\n",
    "        return res\n",
    "\n",
    "    # 建图函数\n",
    "    def buildGraph(self,numCourses: int, prerequisites: List[List[int]]) -> List[List[int]]:\n",
    "        # 图中共有 numCourses 个节点\n",
    "        graph = [[] for _ in range(numCourses)]\n",
    "        for edge in prerequisites:\n",
    "            from_, to_ = edge[1], edge[0]\n",
    "            # 添加一条从 from 指向 to 的有向边\n",
    "            # 边的方向是「被依赖」关系，即修完课程 from 才能修课程 to\n",
    "            graph[from_].append(to_)\n",
    "        return graph\n",
    "\n",
    "    # 图遍历函数\n",
    "    def traverse(self,graph, s):\n",
    "        if self.onPath[s]:\n",
    "            # 发现环\n",
    "            self.hasCycle[0] = True\n",
    "        if self.visited[s] or self.hasCycle[0]:\n",
    "            return\n",
    "        # 前序遍历位置\n",
    "        self.onPath[s] = True\n",
    "        self.visited[s] = True\n",
    "        for t in graph[s]:\n",
    "            self.traverse(graph, t)\n",
    "        # 后序遍历位置\n",
    "        self.postorder.append(s)\n",
    "        self.onPath[s] = False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # 依赖邻接表\n",
    "        deps = {}\n",
    "        for dep in prerequisites:\n",
    "            if dep[0] not in deps:\n",
    "                deps[dep[0]] = []\n",
    "            deps[dep[0]].append(dep[1])\n",
    "        self.deps = deps\n",
    "        # DFS\n",
    "        self.visiting = [0]*numCourses\n",
    "        self.visited = [0]*numCourses\n",
    "        self.res = []\n",
    "        for i in range(numCourses):\n",
    "            if not self.dfs(i):\n",
    "                return []\n",
    "        return self.res\n",
    "\n",
    "    def dfs(self, i: int) -> bool:\n",
    "        if self.visiting[i]:\n",
    "            return False  # 存在环\n",
    "        if self.visited[i]:\n",
    "            return True  # 已访问过\n",
    "        self.visiting[i] = 1\n",
    "        for pre in self.deps.get(i, []):  # 可能不依赖于任何其他课程\n",
    "            if not self.dfs(pre):\n",
    "                return False\n",
    "        self.res.append(i)\n",
    "        self.visiting[i] = 0\n",
    "        self.visited[i] = 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
    " \n",
    "        # 记录后序遍历结果\n",
    "        postorder = []\n",
    "        # 记录是否存在环\n",
    "        hasCycle = False\n",
    "        visited = [False] * numCourses\n",
    "        onPath = [False] * numCourses\n",
    "\n",
    "        def buildGraph(numCourses: int, prerequisites: List[List[int]]) -> List[List[int]]:\n",
    "            graph = [[] for _ in range(numCourses)]\n",
    "            for x,y in prerequisites:\n",
    "                # 添加一条从 from 指向 to 的有向边\n",
    "                # 边的方向是「被依赖」关系，即修完课程 from 才能修课程 to\n",
    "                graph[y].append(x)\n",
    "            return graph\n",
    "\n",
    "        # 图遍历函数\n",
    "        def traverse(graph, s):\n",
    "            nonlocal hasCycle\n",
    "            if onPath[s]:\n",
    "                # 发现环\n",
    "                hasCycle = True\n",
    "            if visited[s] or hasCycle:\n",
    "                return\n",
    "            # 前序遍历位置\n",
    "            onPath[s] = True\n",
    "            visited[s] = True\n",
    "            for t in graph[s]:\n",
    "                traverse(graph, t)\n",
    "            # 后序遍历位置\n",
    "            postorder.append(s)\n",
    "            onPath[s] = False\n",
    "\n",
    "        graph = buildGraph(numCourses, prerequisites)\n",
    "        # 遍历图\n",
    "        for i in range(numCourses):\n",
    "            traverse(graph, i)\n",
    "        # 有环图无法进行拓扑排序\n",
    "        if hasCycle:\n",
    "            return []\n",
    "        # 逆后序遍历结果即为拓扑排序结果\n",
    "        postorder.reverse()\n",
    "        res = []\n",
    "        for i in postorder:\n",
    "            res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "    graph = [[] for _ in range(numCourses)]\n",
    "    for pair in prerequisites:\n",
    "        course, prereq = pair\n",
    "        graph[prereq].append(course)\n",
    "    visited = [0] * numCourses\n",
    "    result = []\n",
    "    def dfs(course):\n",
    "        if visited[course] == 1:\n",
    "            return False  # 存在环\n",
    "        if visited[course] == 2:\n",
    "            return True  # 已完成访问\n",
    "        visited[course] = 1  # 设置为正在访问\n",
    "        for adj in graph[course]:\n",
    "            if not dfs(adj):\n",
    "                return False\n",
    "        visited[course] = 2  # 设置为已完成访问\n",
    "        result.append(course)  # 添加到结果列表\n",
    "        return True\n",
    "    for i in range(numCourses):\n",
    "        if not dfs(i):\n",
    "            return []\n",
    "    return result[::-1]  # 返回结果列表的逆序，即拓扑排序序列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        graph = [[] for _ in range(numCourses)]\n",
    "        for c, p in prerequisites:\n",
    "            graph[c].append(p)\n",
    "\n",
    "        # DFS\n",
    "        hasCycle = False\n",
    "        visited = [False] * numCourses\n",
    "        onPath = [False] * numCourses\n",
    "        paths = []\n",
    "        def DFS(node):\n",
    "            nonlocal hasCycle\n",
    "            nonlocal visited\n",
    "            nonlocal onPath\n",
    "            nonlocal paths\n",
    "            if onPath[node]:\n",
    "                hasCycle = True\n",
    "            if hasCycle or visited[node]:\n",
    "                return\n",
    "            visited[node] = True\n",
    "            onPath[node] = True\n",
    "            for neigh in graph[node]:\n",
    "                DFS(neigh)\n",
    "            paths.append(node)\n",
    "            onPath[node] = False\n",
    "            return\n",
    "        \n",
    "        for n in range(numCourses):\n",
    "            DFS(n)\n",
    "        if hasCycle:\n",
    "            return []\n",
    "        return paths\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-03a72/huan-jian--e36de/\n",
    "# 直观地说就是，让你把一幅图「拉平」，而且这个「拉平」的图里面，所有箭头方向都是一致的，比如上图所有箭头都是朝右的。\n",
    "# 很显然，如果一幅有向图中存在环，是无法进行拓扑排序的，因为肯定做不到所有箭头方向一致；反过来，如果一幅图是「有向无环图」，那么一定可以进行拓扑排序\n",
    "\n",
    "# 将后序遍历的结果进行反转，就是拓扑排序的结果。\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # 记录一次 traverse 递归经过的节点。\n",
    "        self.onPath = []\n",
    "        # 记录遍历过的节点，防止走回头路\n",
    "        self.visited = []\n",
    "        # 记录图中是否有环\n",
    "        self.hasCycle = False\n",
    "        # 记录最终结果\n",
    "        self.postorder = []\n",
    "\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # 记录一次traverse递归所经过的节点\n",
    "        self.onPath = [False] * numCourses\n",
    "        self.visited = [False] * numCourses\n",
    "\n",
    "        # 创建邻接表\n",
    "        # 邻接表的定义：每个节点（也就是[[], []]）(也就是里面的每个小列表的idx)，的list里装着他的邻居\n",
    "        graph = self.buildGraph(numCourses, prerequisites)\n",
    "\n",
    "        # 遍历图中的所有节点\n",
    "        for i in range(numCourses):\n",
    "            # 遍历第i个节点\n",
    "            self.traverse(graph, i)\n",
    "        \n",
    "        # 有环图无法进行拓扑排序\n",
    "        if self.hasCycle:\n",
    "            return []\n",
    "        \n",
    "        # 只要没有循环依赖可以完成所有课程\n",
    "        self.postorder.reverse()\n",
    "        res = [i for i in self.postorder]\n",
    "        return res\n",
    "\n",
    "    def buildGraph(self, numCourses, prerequisites):\n",
    "        # 创建邻接表，图中共有 numCourses 个节点\n",
    "        graph = [[] for _ in range(numCourses)]\n",
    "\n",
    "        for to_, from_ in prerequisites:\n",
    "            # 这句代码的意思是：graph中，idx为from_（先修完）的节点，他的邻居有to_节点（才能修他）\n",
    "            # 修完课程 from_ 才能修课程 to\n",
    "            # 在图中添加一条从 from_ 指向 to 的有向边\n",
    "            graph[from_].append(to_)\n",
    "        \n",
    "        return graph\n",
    "\n",
    "    def traverse(self, graph, s):\n",
    "        if self.onPath[s]:\n",
    "            # 出现环\n",
    "            self.hasCycle = True\n",
    "            return\n",
    "        \n",
    "        if self.visited[s] or self.hasCycle:\n",
    "            # 如果已经遍历过，或者已经找到了环，也不用再遍历了\n",
    "            return\n",
    "        \n",
    "        # 前序遍历代码位置，做选择\n",
    "        self.visited[s] = True\n",
    "        self.onPath[s] = True\n",
    "    \n",
    "        # 递归\n",
    "        for p in graph[s]:\n",
    "            self.traverse(graph, p)\n",
    "        \n",
    "        # 后序遍历代码位置\n",
    "        self.postorder.append(s)\n",
    "        # 撤销选择\n",
    "        self.onPath[s] = False\n",
    "\n",
    "            \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        lst = [[] for _ in range(numCourses)]\n",
    "        for a, b in prerequisites:\n",
    "            lst[b].append(a)\n",
    "        \n",
    "        res, hasCycle = [], False\n",
    "        visited, onPath = [False] * numCourses, [False] * numCourses\n",
    "\n",
    "        def dfs(i):\n",
    "            if onPath[i]:\n",
    "                nonlocal hasCycle\n",
    "                hasCycle = True\n",
    "            if onPath[i] or visited[i]:\n",
    "                return\n",
    "            onPath[i] = True\n",
    "            visited[i] = True\n",
    "            for j in lst[i]:\n",
    "                dfs(j)\n",
    "            onPath[i] = False\n",
    "            res.append(i)\n",
    "        \n",
    "        for i in range(numCourses):\n",
    "            dfs(i)\n",
    "        return [] if hasCycle else res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        if len(prerequisites)==0:\n",
    "            return [i for i in range(numCourses)]\n",
    "        privor = [[] for _ in range(numCourses)]\n",
    "        for a,b in prerequisites:\n",
    "            privor[b].append(a)\n",
    "        # visited = [0]*numCourses\n",
    "        # hascycle = False\n",
    "        # def has_cycle(i):\n",
    "        #     nonlocal hascycle\n",
    "        #     if visited[i]==-1:\n",
    "        #         hascycle = True\n",
    "        #     if hascycle or visited[i]==1:\n",
    "        #         return\n",
    "        #     visited[i] = -1\n",
    "        #     for j in privor[i]:\n",
    "        #         has_cycle(j)\n",
    "        #     visited[i] = 1\n",
    "        # for i in range(numCourses):\n",
    "        #     has_cycle(i)\n",
    "        # if hascycle:\n",
    "        #     return []\n",
    "        res = []\n",
    "        visited = [0]*numCourses\n",
    "        # on_path = [0]*numCourses\n",
    "        hascycle = False\n",
    "        def traverse(i):\n",
    "            nonlocal hascycle\n",
    "            if visited[i] == -1:\n",
    "                hascycle = True\n",
    "            if hascycle or visited[i]==1:\n",
    "                return\n",
    "            visited[i] = -1\n",
    "            for j in privor[i]:\n",
    "                traverse(j)\n",
    "            res.append(i)\n",
    "            visited[i]=1\n",
    "        for i in range(numCourses):\n",
    "            traverse(i)\n",
    "        return [] if hascycle else res[::-1]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        visited = [0] * numCourses\n",
    "        adjacent = [[] for _ in range(numCourses)]\n",
    "\n",
    "        def dfs(i):\n",
    "            if visited[i] == 1:\n",
    "                return False\n",
    "            if visited[i] == 2:\n",
    "                return True\n",
    "            visited[i] = 1\n",
    "            for j in adjacent[i]:\n",
    "                if not dfs(j):\n",
    "                    return False\n",
    "\n",
    "            visited[i] = 2\n",
    "            res.append(i)\n",
    "            return True\n",
    "        for cur, pre in prerequisites:\n",
    "            adjacent[cur].append(pre)\n",
    "        for i in range(numCourses):\n",
    "            if not dfs(i):\n",
    "                return []\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        def dfs(i):\n",
    "            nonlocal adj \n",
    "            nonlocal flags\n",
    "            nonlocal res \n",
    "\n",
    "            if flags[i] == 2:\n",
    "                return True \n",
    "            if flags[i] == 1:\n",
    "                return False \n",
    "            \n",
    "            flags[i] = 1 \n",
    "            for j in adj[i]:\n",
    "                if not dfs(j):\n",
    "                    return False \n",
    "            \n",
    "            flags[i] = 2\n",
    "            res.append(i)\n",
    "            return True  \n",
    "\n",
    "        adj = [[] for _ in range(numCourses)]\n",
    "        flags = [0 for _ in range(numCourses)]\n",
    "\n",
    "        res = []\n",
    "        for i in range(len(prerequisites)):\n",
    "            curr, pre = prerequisites[i][0], prerequisites[i][1]\n",
    "            adj[curr].append(pre)\n",
    "        \n",
    "        for i in range(numCourses):\n",
    "            if not dfs(i):\n",
    "                return []\n",
    "        \n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "\n",
    "\n",
    "\n",
    "        graph = collections.defaultdict(list)\n",
    "\n",
    "        for c, p in prerequisites:\n",
    "            graph[p].append(c)\n",
    "\n",
    "        res = []\n",
    "\n",
    "        STATE = [0] * numCourses\n",
    "        valid = True\n",
    "        def dfs(idx):\n",
    "            nonlocal valid\n",
    "            STATE[idx] = 1\n",
    "            for nex in graph[idx]:\n",
    "                if STATE[nex] == 1:\n",
    "                    valid = False\n",
    "                    return\n",
    "                elif STATE[nex] == 0:\n",
    "                    dfs(nex)\n",
    "                    if not valid:\n",
    "                        return \n",
    "            res.append(idx)\n",
    "            STATE[idx] = 2\n",
    "\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            if valid and STATE[i] == 0:\n",
    "                dfs(i)\n",
    "        return res[::-1] if valid else []\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # 存储有向图\n",
    "        import collections\n",
    "        edges = collections.defaultdict(list)\n",
    "        # 标记每个节点的状态：0未搜索，1搜索中，2已完成\n",
    "        visited = [0] * numCourses\n",
    "        # 用栈来记录结果\n",
    "        result = list()\n",
    "        # 判断有向图中是否有环\n",
    "        valid = True\n",
    "\n",
    "        for info in prerequisites:\n",
    "            edges[info[1]].append(info[0])\n",
    "\n",
    "        def dfs(u):\n",
    "            nonlocal valid\n",
    "            # 将节点标记为搜索中\n",
    "            visited[u] = 1\n",
    "            for v in edges[u]:\n",
    "                if visited[v] == 0:\n",
    "                    dfs(v)\n",
    "                    if not valid:\n",
    "                        return \n",
    "                elif visited[v] == 1:\n",
    "                    valid = False\n",
    "                    return \n",
    "            # 将节点标记为已完成\n",
    "            visited[u] = 2\n",
    "            result.append(u)\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            if valid and not visited[i]:\n",
    "                dfs(i)\n",
    "\n",
    "        if not valid:\n",
    "            return []\n",
    "\n",
    "        return result[::-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        if numCourses == 1:\n",
    "            return [0]\n",
    "        edges = [[] for i in range(numCourses)]\n",
    "        for i in range(len(prerequisites)):\n",
    "            edges[prerequisites[i][1]].append(prerequisites[i][0])\n",
    "\n",
    "        ans = []\n",
    "        visited = [0] * numCourses\n",
    "        valid = True\n",
    "        def dfs(i):\n",
    "            nonlocal valid\n",
    "            visited[i] = 1\n",
    "            for j in edges[i]:\n",
    "                if visited[j] == 0:\n",
    "                    dfs(j)\n",
    "                elif visited[j] == 1:\n",
    "                    valid = False\n",
    "                    return\n",
    "            ans.append(i)\n",
    "            visited[i] = 2\n",
    "        \n",
    "        for i in range(numCourses):\n",
    "            if visited[i] == 0:\n",
    "                dfs(i)\n",
    "            if not valid:\n",
    "                return []\n",
    "        if not valid:\n",
    "            return []\n",
    "        return ans[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        # 广度优先搜素\n",
    "        res = []\n",
    "        edges = collections.defaultdict(list)\n",
    "        visited = [0] * numCourses\n",
    "        valid = True\n",
    "        for u, v in prerequisites:\n",
    "            edges[v].append(u)\n",
    "        \n",
    "        def dfs(u: int):\n",
    "            nonlocal valid\n",
    "            visited[u] = 1\n",
    "            for v in edges[u]:\n",
    "                if visited[v] == 0:\n",
    "                    dfs(v)\n",
    "                    if valid is False:\n",
    "                        return\n",
    "                elif visited[v] == 1:\n",
    "                    valid = False\n",
    "                    return\n",
    "            res.append(u)\n",
    "            visited[u] = 2\n",
    "        for i in range(numCourses):\n",
    "            if valid and not visited[i]:\n",
    "                dfs(i)\n",
    "        \n",
    "        return res[::-1] if len(res) == numCourses else []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        edges = {}\n",
    "        for i in range(numCourses):\n",
    "            edges[i] = []\n",
    "        visited = [0] * numCourses\n",
    "        result = []\n",
    "        valid = True\n",
    "\n",
    "        for info in prerequisites:\n",
    "            edges[info[0]].append(info[1])\n",
    "        \n",
    "        def dfs(u):\n",
    "            nonlocal valid\n",
    "            visited[u] = 1 # searching\n",
    "            for v in edges[u]: # neighbor\n",
    "                if visited[v] == 0: # not searching\n",
    "                    dfs(v)\n",
    "                    if not valid:\n",
    "                        return\n",
    "                elif visited[v] == 1: # back to searching\n",
    "                    valid = False\n",
    "                    return\n",
    "            \n",
    "            # current node's neighbor searched\n",
    "            visited[u] = 2\n",
    "            result.append(u)\n",
    "        \n",
    "        for i in range(numCourses):\n",
    "            if valid and visited[i] == 0:\n",
    "                dfs(i)\n",
    "        if not valid:\n",
    "            return []\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        edges = collections.defaultdict(list)\n",
    "        visited = [0] * numCourses\n",
    "        result = list()\n",
    "        valid = True\n",
    "        for info in prerequisites:\n",
    "            edges[info[1]].append(info[0])\n",
    "\n",
    "        def dfs(u):\n",
    "            nonlocal valid\n",
    "            visited[u] = 1\n",
    "            for v in edges[u]:\n",
    "                if visited[v] == 0:\n",
    "                    dfs(v)\n",
    "                    if not valid: return\n",
    "                elif visited[v] == 1:\n",
    "                    valid = False\n",
    "                    return\n",
    "            visited[u] = 2\n",
    "            result.append(u)\n",
    "        \n",
    "        for i in range(numCourses):\n",
    "            if valid and not visited[i]:\n",
    "                dfs(i)\n",
    "        \n",
    "        if not valid:\n",
    "            return list()\n",
    "\n",
    "        return result[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:\n",
    "        edges = collections.defaultdict(list)\n",
    "        visited = [0] * numCourses\n",
    "        result = []\n",
    "        valid = True\n",
    "        for info in prerequisites:\n",
    "            edges[info[1]].append(info[0])\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal valid\n",
    "            visited[i] = 1\n",
    "            for j in edges[i]:\n",
    "                if visited[j] == 0:\n",
    "                    dfs(j)\n",
    "                    if not valid:\n",
    "                        return\n",
    "                elif visited[j] == 1:\n",
    "                    valid = False\n",
    "                    return\n",
    "            visited[i] = 2\n",
    "            result.append(i)\n",
    "\n",
    "        for i in range(numCourses):\n",
    "            if valid and not visited[i]:\n",
    "                dfs(i)\n",
    "\n",
    "        if not valid:\n",
    "            return []\n",
    "\n",
    "        return result[::-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
